home *** CD-ROM | disk | FTP | other *** search
/ Amiga Tools 5 / Amiga Tools 5.iso / grafik / converter / limbo4.0 / src / 2d / encode.c < prev    next >
Encoding:
C/C++ Source or Header  |  1996-07-16  |  15.4 KB  |  487 lines
  1. #include "includes.h"
  2.  
  3.  Parameter *Encode_Parm;
  4.  BitMap  *Encode_Block;
  5.  BitMap  *Encode_Image;
  6.  unsigned char Encode_DeltaQuant;
  7.  int Encode_PostTrans;
  8.  
  9.  
  10. /**************************************|****************************************
  11. Routine   : GetClassCount
  12. Input  par: FeatureSpace *S (pointer to feature space)
  13.             int *Index (pointer to index in the feature space)
  14. Output par: unsigned long (count of subclass members)
  15. Function  : Finds the number of nodes in a given subclass of a feature space.
  16. ***************************************|***************************************/
  17.  
  18.  unsigned long GetClassCount(FeatureSpace *S,int *Index)
  19.   {
  20.    int i;
  21.    Grid *tmp=S->GridArray;
  22.    GridTerm *T;
  23.    for(i=0;i<S->Dimension;i++) tmp=tmp->Next[Index[i]];
  24.    T=(GridTerm *)tmp;
  25.    return T->Count;
  26.   }
  27.  
  28. /**************************************|****************************************
  29. Routine   : FindNearest
  30. Input  par: ListNode *List (pointer to list of domain blocks)
  31.             PoolNode *Range(range block to compare to)
  32.             int dim  (feature dimension)
  33.             int MaxList (maximum nodes in list)
  34. Output par: ListNode * (pointer to found list)
  35. Function  : Finds the nearest domain blocks for a given range block in the 
  36.             n-dimensional feature space.
  37. ***************************************|***************************************/
  38.  
  39.  ListNode *FindNearest(ListNode *List,PoolNode *Range,int dim, int MaxList)
  40.   {
  41.    ListNode *s=List,*NewList=GimmeAListNode();/* this routine has to be very quick since its */
  42.    ListNode *Tmp,*p;                          /* called at least once for every edge range block */
  43.    register unsigned int i;
  44.    register unsigned long d;
  45.    unsigned int Found=1;
  46.    register long t;
  47.    
  48.    NewList->Next=NewList->Pred=NewList;
  49.    NewList->Domain=List->Domain;
  50.    
  51.    d=0;   /* find first distance */
  52.    i=dim;
  53.    while(i--) 
  54.     {
  55.      t=Range->Distance[i]-List->Domain->Distance[i];
  56.      if (t>0) d += t; /* Manhattan distance for speed */
  57.      else d -=t;
  58.     }
  59.    
  60.    NewList->L=d; /* initialize new list */
  61.    List=List->Next;
  62.    
  63.    while(List!=NULL)
  64.     {
  65.      d=0;
  66.      i=dim;
  67.      while(i--)
  68.       {
  69.        t=Range->Distance[i]-List->Domain->Distance[i];
  70.        if (t>0) d += t; /* Manhattan distance for speed */
  71.        else d -=t;
  72.       }
  73.      
  74.      p=NewList;
  75.      
  76.      if(Found<=MaxList)
  77.       {
  78.        Found++;
  79.        
  80.        Tmp=GimmeAListNode();
  81.        Tmp->Domain=List->Domain;
  82.        Tmp->L=d;
  83.        
  84.        while((p->L<d) && (p->Next!=NewList)) p=p->Next;
  85.        
  86.        if(p->L<d) p=p->Next; /* check for last in list */
  87.        
  88.        Tmp->Pred=p->Pred;
  89.        Tmp->Pred->Next=Tmp;
  90.        Tmp->Next=p;
  91.        p->Pred=Tmp;
  92.        if (d<=NewList->L) NewList=Tmp; /* new list start */
  93.       }
  94.      else
  95.      if (p->Pred->L>d)
  96.       {
  97.        while(p->L<d) p=p->Next;
  98.        
  99.        Tmp=NewList->Pred; /* last one in list */
  100.        Tmp->Domain=List->Domain;
  101.        Tmp->L=d;
  102.        
  103.        if(p->Next!=NewList && p!=NewList) /* new element not last in list */
  104.         {
  105.          NewList->Pred=Tmp->Pred;     /* reset last list meber */
  106.          NewList->Pred->Next=NewList;
  107.          
  108.          Tmp->Pred=p->Pred;   /* insert member */
  109.          Tmp->Pred->Next=Tmp;
  110.          Tmp->Next=p;
  111.          p->Pred=Tmp;
  112.         }
  113.        if (d<=NewList->L) NewList=Tmp; /* new list start */          
  114.       }
  115.      List=List->Next;
  116.     }
  117.    
  118.    FreeMeAList(s);
  119.    return NewList;
  120.   }
  121.  
  122. /**************************************|****************************************
  123. Routine   : BuildList
  124. Input  par: FeatureSpace *S (pointer to a feature space)
  125.             int *Index (pointer to index in a feature space)
  126. Output par: ListNode * (pointer created list)
  127. Function  : Takes a subclass of a feature space (pointed out by the index) and
  128.             builds a list of the blocks in the class.
  129. ***************************************|***************************************/
  130.  
  131.  ListNode *BuildList(FeatureSpace *S,int *Index)
  132.   {
  133.    int i;
  134.    ListNode *Start,*List,*tmpList;
  135.    Grid *tmp=S->GridArray;
  136.    GridTerm *T;
  137.    
  138.    for(i=0;i<S->Dimension;i++) tmp=tmp->Next[Index[i]];
  139.    T=(GridTerm *)tmp;
  140.    
  141.    if (T->Count==0) return (ListNode *)NULL;
  142.    
  143.    tmpList=T->Class;
  144.    Start=List=GimmeAListNode();
  145.    List->Info=T->Count;
  146.    List->Domain=tmpList->Domain;
  147.    tmpList=tmpList->Next;
  148.    
  149.    while (tmpList!=NULL)
  150.     {
  151.      ListNode *pp=GimmeAListNode();
  152.      
  153.      List->Next=pp;
  154.      pp->Pred=List;
  155.      List=List->Next;
  156.      List->Domain=tmpList->Domain;
  157.      tmpList=tmpList->Next;
  158.     }
  159.    
  160.    List->Next=Start;
  161.    Start->Pred=List;
  162.    
  163.    return Start;
  164.   }
  165.  
  166. /**************************************|****************************************
  167. Routine   : InsertList
  168. Input  par: ListNode *List (first list)
  169.             ListNode *Xtra (second list)
  170. Output par: ListNode * (pointer to meged lists)
  171. Function  : Merges to lists.
  172. ***************************************|***************************************/
  173.  
  174.  ListNode *InsertList(ListNode *List,ListNode *Xtra)
  175.   {
  176.    if(Xtra==NULL) return List;
  177.    if(List==NULL) return Xtra;
  178.    
  179.    if (Xtra->Info==0) return List;
  180.    if (List->Info==0) return Xtra;
  181.    
  182.    List->Pred->Next=Xtra;
  183.    List->Pred=Xtra->Pred;
  184.    Xtra->Pred->Next=List;
  185.    Xtra->Pred=List->Pred;
  186.    List->Info +=Xtra->Info;
  187.    
  188.    return List;
  189.   }
  190.  
  191. /**************************************|****************************************
  192. Routine   : XtraSearch
  193. Input  par: FeatureSpace *S (pointer the feature space)
  194.             ListNode *List  (list of blocks found so far)
  195.             int *Index (pointer to rangenode index)
  196.             int shell  (the new shell to be search in (in the feature space))
  197.             int dim (feature space dimension)
  198.             int end (end flag)
  199. Output par: ListNode * (pointer to new list of blocks found)
  200. Function  : A really special routine to do an extra search in an n-dimensional
  201.             feature space. In the case where a normal search do not find enough
  202.             blocks this routine is called. It looks searches in the surrounding 
  203.             of the original block index (shell).
  204. ***************************************|***************************************/
  205.  
  206.  ListNode *XtraSearch(FeatureSpace *S,ListNode *List,int *Index,int shell,int dim,int end)
  207.   {
  208.    int *NewIndex=GimmeAIntArray(S->Dimension); /* this routine gave me a lot of trouble ! */
  209.    ListNode *L1,*L2;
  210.    register int i,j;
  211.    int d=dim,flag;
  212.    d++;
  213.    
  214.    for(j= -shell;j<= shell;j++)
  215.     {
  216.      for(i=0;i<S->Dimension;i++) NewIndex[i]=Index[i];
  217.      NewIndex[dim] += j;
  218.      
  219.      flag=TRUE;
  220.      for(i=0;i<S->Dimension;i++) if (NewIndex[i]<0 || NewIndex[i]>=S->Size) flag=FALSE;
  221.      
  222.      if ((j== -shell || j== shell || end) && d==S->Dimension && flag)
  223.       {
  224.        L1=BuildList(S,NewIndex);
  225.        List=InsertList(List,L1);
  226.       }
  227.      
  228.      if (d<=S->Dimension && flag)
  229.       {
  230.        if (j== -shell || j== shell || end) L2=XtraSearch(S,NULL,NewIndex,shell,d,TRUE);
  231.        else L2=XtraSearch(S,NULL,NewIndex,shell,d,FALSE);
  232.        List=InsertList(List,L2);
  233.       }
  234.     }
  235.    
  236.    FreeMeAIntArray(NewIndex);
  237.    
  238.    return List;
  239.   }
  240.  
  241. /**************************************|****************************************
  242. Routine   : SearchGrid
  243. Input  par: FeatureSpace *DomainS (pointer to domain feature space)
  244.             PoolNode *RangeNode   (pointer to range block)
  245.             int MinList,int MaxList (list sizes)
  246. Output par: ListNode * (pointer to list of domain blocks)
  247. Function  : Find the nearest domain blocks for a given range block in an n-
  248.             dimensional feature space.
  249. ***************************************|***************************************/
  250.  
  251.  ListNode *SearchGrid(FeatureSpace *DomainS,PoolNode *RangeNode,int MinList,int MaxList)
  252.   {
  253.    ListNode *SearchList;
  254.    int Dim=DomainS->Dimension;
  255.    int i,c=0;
  256.    
  257.    SearchList=BuildList(DomainS,RangeNode->Index);
  258.    
  259.    while (((SearchList==NULL) || (SearchList->Info<MinList)) && (c<10))    
  260.     {
  261.      c++; /* he he : c plus plus */
  262.      SearchList=XtraSearch(DomainS,SearchList,RangeNode->Index,c,0,FALSE);
  263.     }
  264.    if (c>1) vprintf(stderr," %d",c);
  265.    
  266.    if (SearchList==NULL)
  267.     {
  268.      vprintf(stderr,"\n search failed: ");
  269.      for(i=0;i<Dim;i++) vprintf(stderr," %d ",RangeNode->Index[i]);
  270.      exit(10);
  271.      /* for(i=0;i<Dim;i++) I[i]=(DomainS->Size)>>1;
  272.      SearchList=ExtraSearch(DomainS,SearchList,I,1);
  273.      vprintf(stderr,".",SearchList->Info);*/
  274.     }
  275.    
  276.    SearchList->Pred->Next=NULL; /* terminate list */
  277.    if (SearchList->Info>MaxList)
  278.    SearchList=FindNearest(SearchList,RangeNode,DomainS->Dimension,MaxList);
  279.    
  280.    return SearchList;
  281.   }
  282.  
  283. /**************************************|****************************************
  284. Routine   : FindTransformation3D
  285. Input  par: int XPos,int YPos, int ZPos (position of block to be encoded)
  286.             int NSquare (the quadtree level)
  287.             int BlockSize (range blocksize)
  288.             PoolStructure *Pool (pool structure !)
  289.             int MinList,int MaxList (list sizes)
  290. Output par: Transformation * (pointer to the found transformation)
  291. Function  : Encodes a specific range block.
  292. ***************************************|***************************************/
  293.  
  294.  Transformation *FindTransformation(int XPos,int YPos, int NSquare,
  295.                                       int BlockSize,PoolStructure *Pool,
  296.                                       int MinList,int MaxList)
  297.   {
  298.    register unsigned int x,y,D=BlockSize<<1;
  299.    Transformation *Trans=GimmeATransformation();
  300.    PoolNode *RNode;
  301.    ListNode *SearchList,*List;
  302.    float *Features;
  303.    
  304.    Trans->BlockSize=BlockSize;
  305.    Trans->D=D;
  306.    
  307.    RNode=Pool->RangeNodes[XPos/BlockSize][YPos/BlockSize];
  308.    Features=RNode->Features;
  309.    
  310.    Encode_Block->XSize=Encode_Block->YSize=BlockSize;
  311.    
  312.    if(RNode->Distance==NULL)
  313.     {
  314.      Trans->Type=SHADEBLOCK;  /* find shade transformation */
  315.      Trans->g0  =Features[MEAN];
  316.     }
  317.    else /* find edge transformtion */
  318.     {
  319.      float Alpha,temp,tt;
  320.      int Deltag;
  321.      register long Bestdm=LONG_MAX,dm,Newdm;
  322.      PoolNode *DNode;
  323.      BitMap   *tempimg;
  324.      int tn,Count=0;
  325.      register unsigned int i,j,x,y;
  326.      
  327.      Trans->Type=EDGEBLOCK;
  328.      if(Encode_Parm->TPostProcess>=0)
  329.      List=SearchList=SearchGrid(Pool->DomainSpace,RNode,MinList+POSTLISTEXTRA,MaxList+POSTLISTEXTRA);
  330.      else      
  331.      List=SearchList=SearchGrid(Pool->DomainSpace,RNode,MinList,MaxList);
  332.      
  333.      while ((List->Next!=NULL) && (Count<MaxList) && (List->Next!=SearchList))
  334.       {
  335.        DNode=List->Domain;
  336.        if (DNode->Features[VAR]==0.0) ErrorHandler(OUT_OF_RANGE,"Null variance"); /* should not happen ! */
  337.  
  338.        tempimg=Pool->SampledDomainBitmap;
  339.        x=DNode->x>>1;
  340.        y=DNode->y>>1;
  341.        
  342.        tt=temp=Features[STDDEV]/DNode->Features[STDDEV]; 
  343. /*
  344.        temp=0.0;
  345.        for(i=0;i<Encode_Block->XSize;i++)    
  346.        for(j=0;j<Encode_Block->YSize;j++)
  347.         {
  348.          temp += (float)tempimg->Map[x+i][y+j]*(float)Encode_Image->Map[XPos+i][YPos+j];
  349.         }
  350.  
  351.        temp = temp/((float)Encode_Block->XSize*(float)Encode_Block->YSize); 
  352.        temp = (temp-(Features[MEAN])*(DNode->Features[MEAN]))/(DNode->Features[VAR]); 
  353. */ 
  354.        Alpha=MakeFloat(MakeRange(temp,Encode_Parm),Encode_Parm); /* quant alpha */
  355.  
  356. /*       vprintf(stderr,"\na %f\t\t%f\t%f\t%f",Alpha,temp,
  357.        Features[MEAN]*DNode->Features[MEAN],temp-Features[MEAN]*DNode->Features[MEAN]); 
  358. */
  359.        Deltag=(int)(Features[MEAN]-DNode->Features[MEAN]*Alpha); 
  360.        
  361.        if (Deltag> Encode_DeltaQuant) Deltag= Encode_DeltaQuant;
  362.        if (Deltag<-Encode_DeltaQuant) Deltag=-Encode_DeltaQuant;
  363.        
  364.        for(i=0;i<Encode_Block->XSize;i++)    
  365.        for(j=0;j<Encode_Block->YSize;j++)
  366.        Encode_Block->Map[i][j]=(tempimg->Map[x+i][y+j]*Alpha)+Deltag;
  367.       
  368.        dm=LONG_MAX;
  369.        for(i=1;i<=8;i++)
  370.         {
  371.          Newdm=IsoAnddl2(Encode_Image,XPos,YPos,Encode_Block,BlockSize,i);
  372.          if(Newdm<dm)
  373.           {
  374.            dm=Newdm;
  375.            tn=i;
  376.           }
  377.         }
  378.  
  379.  
  380.        if(dm<Bestdm)
  381.         {
  382.          Bestdm=dm;
  383.          Trans->Alpha=Alpha;
  384.          Trans->Deltag=Deltag;
  385.          Trans->tn=tn-1;
  386.          Trans->Domain=DNode;
  387.          Trans->Distortion=dm;
  388.         }
  389.        Count++;
  390.        List=List->Next;
  391.        
  392.        /* now check the distortion and postprocess if necessary */
  393.        
  394.        if (Count==MaxList && Encode_Parm->TPostProcess>=0)
  395.        if(Encode_Parm->TPostProcess<Trans->Distortion/(BlockSize*BlockSize*BlockSize))      
  396.         {
  397.          MaxList += POSTLISTEXTRA;
  398.          Encode_PostTrans++;
  399.         }
  400.       }
  401.      
  402.      Trans->Distortion /= (BlockSize*BlockSize*BlockSize); /* normalize dl2 */
  403.      FreeMeAList(SearchList);
  404.     }
  405.    
  406.    if(NSquare>0) /* check if there are more sublevels */
  407.     {
  408.      if (Trans->Type==SHADEBLOCK)
  409.       {
  410.        const unsigned int B=BlockSize;
  411.        const register unsigned int val=Trans->g0;
  412.        register int tmp;
  413.        register unsigned long Distortion=0;
  414.        
  415.        for(x=0;x<B;x++) /* insert distortion */
  416.        for(y=0;y<B;y++) 
  417.         {
  418.          tmp=Encode_Image->Map[XPos+x][YPos+y]-val;
  419.          Distortion +=tmp*tmp;
  420.         }
  421.        Trans->Distortion=Distortion/(B*B*B);
  422.       }
  423.      
  424.      if(Trans->Distortion>(unsigned long)Encode_Parm->TMainSub) /* check distortion */
  425.       {
  426.        Trans->Type=NOBLOCK; /* unmark main block */
  427.        
  428.        Trans->Sub=GimmeATransArray(2,2);
  429.        for(x=0;x<2;x++)
  430.        for(y=0;y<2;y++)
  431.        Trans->Sub[x][y]= /* encode ALL sub blocks */
  432.        FindTransformation(XPos+x*(BlockSize>>1),YPos+y*(BlockSize>>1),
  433.                             NSquare-1,BlockSize>>1,
  434.                             Pool->Next,MinList,MaxList);
  435.       }
  436.     }
  437.    
  438.    return Trans;
  439.   }
  440.  
  441. /**************************************|****************************************
  442. Routine   : Encode3D
  443. Input  par: BitMap3D *Image (pointer to the image to encode)
  444.             int NSquare     (number of octree square levels)
  445.             int StartBlockSize (maximum range block size)
  446.             PoolStructure *Pool(pointer to poolstructure)
  447.             Parameter *Pa   (pointer to parameters)
  448.             int MinList,int MaxList (list sizes)
  449. Output par: Transformation **** (pointer to 3d array of transformations)
  450. Function  : Encodes the image. Finds the a fractal transformations for every
  451.             range block.
  452. ***************************************|***************************************/
  453.  
  454.  Transformation ***Encode(BitMap *Image,int NSquare,int StartBlockSize,
  455.                              PoolStructure *Pool,Parameter *Pa,int MinList,int MaxList)
  456.   {
  457.    register unsigned int x,y;
  458.    Transformation ***FCCodes=GimmeATransArray(Image->XSize/StartBlockSize,
  459.                                                  Image->YSize/StartBlockSize);
  460.    vprintf(stderr,"\nEncoding...");
  461.    
  462.    Encode_Parm=Pa; /* make parmeters global for module */  
  463.    Encode_DeltaQuant=1<<(Pa->DBits-1)-1;
  464.    Encode_Block=GimmeABitMap(StartBlockSize,StartBlockSize,Image->ImgType);
  465.    Encode_Image=Image;
  466.    Encode_PostTrans=0;
  467.    
  468.    for(x=0;x<Image->XSize/StartBlockSize;x++)
  469.     {
  470.      for(y=0;y<Image->YSize/StartBlockSize;y++)
  471.      FCCodes[x][y]=FindTransformation(x*StartBlockSize,y*StartBlockSize,
  472.                                            NSquare,StartBlockSize,Pool,MinList,MaxList);
  473.      
  474.      if (Quiet) fprintf(stderr,"%3.1f%c ",(float)(x*100)/Image->XSize,'%');
  475.      else fprintf(stderr,"\n   x:%3d y:%d =%3.1f%c",x*StartBlockSize,y*StartBlockSize,
  476.                  (float)(x*StartBlockSize*100)/Image->XSize,'%');
  477.    }
  478.  
  479.    vprintf(stderr,"\n   Post processed %d blocks",Encode_PostTrans);
  480.    Encode_Block->XSize=StartBlockSize;
  481.    Encode_Block->YSize=StartBlockSize;
  482.    
  483.    FreeMeABitMap(Encode_Block);
  484.    
  485.    return FCCodes;
  486.   }
  487.